#include <QString>
#include <vector>
#include <iostream>
#include <QFile>
#include <QTextStream>
#include <QLinkedList>
#include <QDebug>

#include "pupil.h"

using namespace std;

void quickSort( Pupil** students, int l, int r, int subjectIndex)
{
    Pupil* pupilLeft;
    Pupil* pupilRight;
    Pupil* middleElement;

    int right = r;
    int left = l;

    pupilLeft = students[left];
    pupilRight = students[right];
    middleElement = students[( left + right ) / 2];

    do {
        while(pupilLeft->getBall(subjectIndex) < middleElement->getBall(subjectIndex))
        {
            left++;
            pupilLeft = students[left];
        }
        while(pupilRight->getBall(subjectIndex) > middleElement->getBall(subjectIndex))
        {
            right--;
            pupilRight = students[right];
        }
        if (left <= right)
        {
            students[left] = pupilRight;
            students[right] = pupilLeft;
            left++;
            pupilLeft = students[left];
            right--;
            pupilRight = students[right];
        }
    } while (left <= right);

    if (left < r) quickSort(students, left, r, subjectIndex);
    if (right > l) quickSort(students, l, right, subjectIndex);
}

void calcGroupBonus(QList<Pupil*>& group, double summ, int subjectIndex, int place)
{
    double groupBonus = summ / group.size();
    QListIterator<Pupil*> groupIterator(group);
    while (groupIterator.hasNext())
    {
        Pupil* pupilInGroup = groupIterator.next();
        pupilInGroup->setBonus(subjectIndex, groupBonus);
        pupilInGroup->setSubjectPlace(subjectIndex, place);
    }
    group.clear();
}

int main(int argc, char *argv[])
{
    QTextStream qtin(stdin);
//    QFile outfile("sort.txt");

//    if (outfile.exists())
//        outfile.remove();

//    outfile.open(QFile::ReadWrite);
//    QTextStream qtout(&outfile);

    int pupilCount;
    qDebug() << "Pupil count: ";
    qtin >> pupilCount;

    Pupil** students = new Pupil*[pupilCount];

    int subjectCount;
    qDebug() << "Subject count: ";
    qtin >> subjectCount;

    // Input

    QString name;
    int ball;
    for (int i = 0; i < pupilCount; i++)
    {
        qDebug() << "Name: ";
        qtin >> name;

        Pupil* pupil = new Pupil(name, subjectCount);
        for (int j = 0; j < subjectCount; j++)
        {
            qDebug() << "Ball[" << j << "] = ";
            qtin >> ball;
            pupil->setBall(j, ball);
        }
        students[i] = pupil;
    }

    for (int j = 0; j < subjectCount; j++)
    {
        // Sort

        quickSort(students, 0, pupilCount-1, j);

        // Set bonuses here
        int currentBall = students[pupilCount - 1]->getBall(j);
        QList<Pupil*> group;
        int bonus = pupilCount;
        double summ = 0;
        int place = 1;

        for (int i = pupilCount - 1; i >= 0; i--, bonus--)
        {
            Pupil* pupil = students[i];
            if (pupil->getBall(j) != currentBall)
            {
                calcGroupBonus(group, summ, j, place);
                group.append(pupil);
                currentBall = pupil->getBall(j);
                summ = bonus;
                place++;
            }
            else
            {
                group.append(pupil);
                summ += bonus;
            }
        }

        if (group.size() > 0)
            calcGroupBonus(group, summ, j, place);
    }

    // Output

    for(int i = pupilCount - 1; i >= 0 ; i--)
    {
        Pupil* pupil = students[i];
        qDebug() << endl << pupil->getName() << " ";
//        qtout << endl << pupil->getName() << " ";

        for (int j = 0; j < subjectCount; j++)
        {
            qDebug() << pupil->getBall(j) << " "
                     << pupil->getBonus(j)
                     << " " << pupil->getSubjectPlace(j);
//            qtout << pupil->getBall(j) << " "
//                  << pupil->getBonus(j)
//                  << " " << pupil->getSubjectPlace(j);
        }
    }

    for (int i = 0; i < pupilCount; i++)
    {
        delete students[i];
    }
    delete students;

//    qtout.flush();
//    outfile.close();

    return 0;
}
